Search for: All records

Merge trees are a valuable tool in the scientific visualization of scalar fields; however, current methods for merge tree comparisons are computationally expensive, primarily due to the exhaustive matching between tree nodes. To address this challenge, we introduce the Merge Tree Neural Network (MTNN), a learned neural network model designed for merge tree comparison. The MTNN enables rapid and high-quality similarity computation. We first demonstrate how to train graph neural networks, which emerged as effective encoders for graphs, in order to to produce embeddings of merge trees in vector spaces for efficient similarity comparison. Next, we formulate the novel MTNN model that further improves the similarity comparisons by integrating the tree and node embeddings with a new topological attention mechanism. We demonstrate the effectiveness of our model on real-world data in different domains and examine our model's generalizability across various datasets. Our experimental analysis demonstrates our approach's superiority in accuracy and efficiency. In particular, we speed up the prior state-of-the-art by more than 100x on the benchmark datasets while maintaining an error rate below 0.1%. 

Recent developments in shape reconstruction and comparison call for the use of many different (topological) descriptor types, such as persistence diagrams and Euler characteristic functions. We establish a framework to quantitatively compare the strength of different descriptor types, setting up a theory that allows for future comparisons and analysis of descriptor types and that can inform choices made in applications. We use this framework to partially order a set of six common descriptor types. We then give lower bounds on the size of sets of descriptors that uniquely correspond to simplicial complexes, giving insight into the advantages of using verbose rather than concise topological descriptors. 

Recent developments in shape reconstruction and comparison call for the use of many different types of topological descriptors (persistence diagrams, Euler characteristic functions, etc.). We establish a framework that allows for quantitative comparisons of topological descriptor types and therefore may be used as a tool in more rigorously justifying choices made in applications. We then use this framework to partially order a set of six common topological descriptor types. In particular, the resulting poset gives insight into the advantages of using verbose rather than concise topological descriptors. We then provide lower bounds on the size of sets of descriptors that are complete discrete invariants of simplicial complexes, both tight and worst case. This work sets up a rigorous theory that allows for future comparisons and analysis of topological descriptor types. 

The combinatorial interpretation of the persistence diagram as a Möbius inversion was recently shown to be functorial. We employ this discovery to recast the Persistent Homology Transform of a geometric complex as a representation of a cellulation on the n-sphere to the category of combinatorial persistence diagrams. Detailed examples are provided. We hope this recasting of the PH transform will allow for the adoption of existing methods from algebraic and topological combinatorics to the study of shapes. 

Learning computer science (CS) is important for careers of tomorrow. Informal CS opportunities, however, are often limited by a student's socioeconomic disposition, location, ethnicity, gender, and ability. In Montana, these limitations are exemplified in rural communities where a dedicated CS teacher is not available. In order to make informal CS opportunities more equitable, we developed culturally responsive outreach modules for students across Montana by using storytelling as a basis of inquiry. In this paper, we present an outreach module based on the Skokomish story of `How Daylight Came to Be.' In this story, the two main characters---Ant and Bear---each dance for Dokweebah (the Changer). Students animate these dances using event-driven programming in the drag-and-drop programming environment Alice. While creating their dances, students construct knowledge of targeted CS concepts and make design decisions based on the context of the story. This outreach module reframes the context and activity of computing in an effort to transform the way in which students see themselves as potential future computer scientists, and democratize computing as a means of telling stories. By using Brayboy's Tribal Critical Race Theory as a theoretical framework for the development of the outreach program, we introduce computing from a lens of American Indian ways of knowing, culture, and power. To demonstrate the effectiveness of this unit in this exploratory study, we describe students' responses to the outreach programs in terms of perceptions of CS and perceptions of Alice as a culturally relevant programming tool. 

This paper presents the first approach to visualize the importance of topological features that define classes of data. Topological features, with their ability to abstract the fundamental structure of complex data, are an integral component of visualization and analysis pipelines. Although not all topological features present in data are of equal importance. To date, the default definition of feature importance is often assumed and fixed. This work shows how proven explainable deep learning approaches can be adapted for use in topological classification. In doing so, it provides the first technique that illuminates what topological structures are important in each dataset in regards to their class label. In particular, the approach uses a learned metric classifier with a density estimator of the points of a persistence diagram as input. This metric learns how to reweigh this density such that classification accuracy is high. By extracting this weight, an importance field on persistent point density can be created. This provides an intuitive representation of persistence point importance that can be used to drive new visualizations. This work provides two examples: Visualization on each diagram directly and, in the case of sublevel set filtrations on images, directly on the images themselves. This work highlights real-world examples of this approach visualizing the important topological features in graph, 3D shape, and medical image data. 

Taking length into consideration while comparing 1D shapes is a challenging task. In particular, matching equal-length portions of such shapes regardless of their combinatorial features, and only based on proximity, is often required in biomedical and geospatial applications. In this work, we define the length-sensitive partial Fréchet similarity (LSFS) between curves (or graphs), which maximizes the length of matched portions that are close to each other and of equal length. We present an exact polynomial-time algorithm to compute LSFS between curves under and . For geometric graphs, we show that the decision problem is NP-hard even if one of the graphs consists of one edge. 

We aim to bring computer science (CS) to rural and American Indian students by blending American Indian storytelling practices with the educational computer programming environment called Alice. The lessons we develop cover CS concepts within the framework of the Content Standards of our state, and the Essential Understandings of American Indians. In this paper, we describe the Plateau Indian Beaded Bags lesson plan, its implementation, and the results of a lesson pilot. In the Plateau Indian Beaded Bags lesson, students learn about the beadwork of Columbia River Plateau-centered tribes. After viewing a picture of a beaded bag with a scene depicting a man on a horse in front of a woman with a tipi in the background, students are asked to construct a story based on this image. They then translate their story into code to create an animation of the story in Alice. Through this hands-on experience, students engage in algorithmic problem solving while using their imagination and creativity, increasing their exposure to, and interest in, CS. 

The Fréchet distance is often used to measure distances between paths, with applications in areas ranging from map matching to GPS trajectory analysis to hand- writing recognition. More recently, the Fréchet distance has been generalized to a distance between two copies of the same graph embedded or immersed in a metric space; this more general setting opens up a wide range of more complex applications in graph analysis. In this paper, we initiate a study of some of the fundamental topological properties of spaces of paths and of graphs mapped to R^n under the Fréchet distance, in an eort to lay the theoretical groundwork for understanding how these distances can be used in practice. In particular, we prove whether or not these spaces, and the metric balls therein, are path-connected.